Un algorithme polynomial pour le problème ouvert du "coupled tasks"

Article dans une revue de vulgarisation.National audienceLa résolution d'un cas particulier du problème d'ordonnancement appelé "coupled tasks" est traité dans ce papier. Une classification en terme de complexité réalisée dans [1] laisse apparaître un cas où la complexité d'un problème est encore ouvert. Il s'agit du cas où ai=a, Li=L, bi=b. Nous proposons un algorithme polynomial en O(n) pour résoudre ce problème. A ce jour il n'a jamais été mis en échec sur un grand nombre de jeux d'essais. La preuve d'optimalité de cet algorithme est établie dans quelques cas